Speculative computing methods may provide greater computing efficiency. In such methods, sections of a sequential computing task may be carried out in parallel according to a “guess” as to how the computing task will proceed. Examples of such speculative computing methods include speculative parallel thread (SPT) compilation and speculative parallel thread (SPT) program execution.
One aspect of performing speculative computing is the prediction of when a particular path should be taken in a computing task. For example, a program may contain several different points at which it may proceed to execute a speculative thread. In speculative computing, the predictions of which regions to speculatively execute during a computing task may effect the efficiency of the computing. The more spurious the predictions are, the less efficient the computing becomes.
An original listing of code may be transformed for SPT execution. This original listing is split into master and speculative threads. A master thread is the primary section of program code that initiates execution of the speculative thread. A speculative thread is the secondary set of code speculatively executed in parallel with the master thread. An ideal partition of master and speculative regions will have no data dependence between the two threads, the threads will have the same size, and the probability of reaching the instruction beginning the speculative thread from the master thread is 1 (i.e., the execution of the master regions always ends at the beginning of the speculative region).
However, most programs do not consist of only ideal partitions of master and speculative threads. In some cases, two code sections may be almost data-independent or their data-independence may be too difficult for a compiler to verify. When such pairs of code sections are speculatively executed in parallel in the SPT model, and a data dependence violation happens during the speculative parallel execution, the master thread must re-execute the speculative thread. If too many dependence violations occur, the cost for re-execution is high and there may be little to no performance gains, or possibly a performance loss.
In order to maximize performance gain, it is beneficial to reduce the expected re-execution cost. The re-execution cost can be reduced by selecting master and speculative threads with a low probability of data dependence between the two threads. Transforming the code so that the data dependence probability between the two threads is a low value may also reduce the re-execution cost. Conventional speculative parallel region algorithms select speculative parallel regions primarily based on control flow independences/probabilities and generate the speculative code after the speculative regions are selected. However, no algorithms apply code transformation and optimization during speculative parallel region selection to generate an optimal set of SPT regions that maximizes the expected overall performance of the code execution.